// Package coding_round_1 25-4
// @Title coding_round_1
// @Description  寻找两个正序数组的中位数
// @Author  == 琳琳也叫王木木 ==  2021/9/15 17:01
// @Create  2021/9/15 17:01
package coding_round_1

// 暴力解法
/**
简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
时间复杂度 O(m+n)
空间复杂度 O(m+n)
*/
// FindMedianSortedArrays 寻找两个正序数组的中位数
func FindMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	count := len(nums2) + len(nums1)
	lastArr := make([]int, count)
	l1, l2 := 0, 0
	i := 0
	for l1 < len(nums1) && l2 < len(nums2) {
		if nums1[l1] < nums2[l2] {
			lastArr[i] = nums1[l1]
			l1++
		} else {
			lastArr[i] = nums2[l2]
			l2++
		}
		i++
	}
	if len(nums1) == l1 {
		for l2 < len(nums2) {
			lastArr[i] = nums2[l2]
			l2++
			i++
		}
	}
	if len(nums2) == l2 {
		for l1 < len(nums1) {
			lastArr[i] = nums1[l1]
			l1++
			i++
		}
	}
	if len(lastArr)%2 == 0 {
		return float64(float64(lastArr[count/2-1]+lastArr[count/2]) / 2)
	}
	return float64(lastArr[count/2])
}

// FindMedianSortedArraysPlus 使用二分查找的方式实现 log(M+N)的时间复杂度
func FindMedianSortedArraysPlus(nums1 []int, nums2 []int) float64 {

	return 0
}
